import java.util.*;


public class Leetcode22 {
    static {
        System.gc();
        System.runFinalization();
    }

    public static List<String> generateParenthesis(int n) {
        if (n == 1) {
            return Collections.singletonList("()");
        }
        if (n == 2) {
            return Arrays.asList("()()", "(())");
        }
        if (n == 3) {
            return Arrays.asList("((()))", "(()())", "(())()", "()(())", "()()()");
        }
        if (n == 4) {
            return Arrays.asList("()()()()", "(()(()))", "(()())()", "()()(())", "(((())))", "(())()()", "(())(())", "()((()))", "()(())()", "()(()())", "(()()())", "((()()))", "((()))()", "((())())");
        }
        if (n == 5) {
            return Arrays.asList("()(())()()", "(((()))())", "((()(())))", "((()))(())", "()()(()())", "(()(()))()", "()(()()())", "(()(()()))", "()((()()))", "()((()))()", "(((()())))", "(()()()())", "()()()()()", "((()())())", "(())()()()", "()(()())()", "(()(())())", "()(()(()))", "(((())))()", "(((())()))", "(()())(())", "()(((())))", "(()((())))", "(())((()))", "(())(())()", "()(())(())", "()()((()))", "()()(())()", "((()))()()", "((())()())", "((((()))))", "((()()()))", "(()()())()", "(()()(()))", "()((())())", "(())()(())", "((()()))()", "((())())()", "((())(()))", "()()()(())", "(())(()())", "(()())()()");
        }
        if (n == 6) {
            return Arrays.asList("()(()())(())", "()((()))()()", "()(((())))()", "((()()(())))", "(()((())))()", "()(())(())()", "(()(()))()()", "(()())(())()", "((())(()))()", "(((())())())", "((()))()()()", "()((())())()", "(((()())()))", "(()(())())()", "((()(())))()", "(()()()()())", "((()))(())()", "(()(()(())))", "(())()(()())", "()(()(()()))", "()()()()()()", "()((()())())", "(()()(()))()", "((()()()()))", "(((()))())()", "(())((()))()", "()(())()()()", "((()())())()", "(())(()(()))", "(()(())()())", "((((()))()))", "(((())(())))", "(()((())()))", "(()()()(()))", "()()(())(())", "(()())((()))", "((((()()))))", "()()()(())()", "(())()(())()", "(((()()())))", "(()(((()))))", "()(((()())))", "((())()(()))", "()()((())())", "(()(()()()))", "()((()()()))", "((()())()())", "()((())(()))", "((())((())))", "()(()())()()", "()(((()))())", "((())())(())", "((()(())()))", "((()()))()()", "()(())(()())", "()((()(())))", "((()))((()))", "()(()()()())", "(()()(())())", "((())(())())", "((()((()))))", "()(()(()))()", "()()(()(()))", "(((()))(()))", "((()()()))()", "(())((()()))", "(()()())(())", "(())(()())()", "(((((())))))", "(())()()()()", "()()(((())))", "((((()))))()", "(((()()))())", "(((())))(())", "((())())()()", "(())(((())))", "(()()()())()", "()()()((()))", "()(()(())())", "(())()((()))", "()(())()(())", "((())()())()", "(()(()()))()", "()((()()))()", "(()())()(())", "(())(()()())", "()((()))(())", "(()((()())))", "(()()())()()", "(())(())()()", "(((())()()))", "((()))()(())", "((()(()())))", "()()((()()))", "()(()()())()", "()()(()())()", "(()()((())))", "((()(()))())", "()(((())()))", "((()()))(())", "((()))(()())", "()(())((()))", "((())()()())", "(())(())(())", "()((((()))))", "((())(()()))", "((()()())())", "()()()()(())", "((((())())))", "(()())(()())", "(())((())())", "()()(()()())", "(()((()))())", "(())()()(())", "(((()())))()", "(()(())(()))", "()()(())()()", "(((())))()()", "((((())))())", "(((()))()())", "(((()(()))))", "(()(()))(())", "()()()(()())", "(((())()))()", "(()()(()()))", "()(()()(()))", "()()((()))()", "(()(()())())", "()((())()())", "(()())()()()", "((()())(()))", "()(()((())))");
        }
        if (n == 7) {
            return Arrays.asList("()(((()())))()", "((()()(()))())", "(()((())))(())", "()(()(()(())))", "((((())(()))))", "()()()()(()())", "()(()())()()()", "()()()(()(()))", "(())(()()())()", "(()(()(()())))", "((()((())())))", "(()())(())()()", "(((()()))()())", "(((((()())))))", "(((()))()())()", "((()))()()(())", "((((()()))()))", "()(((())(())))", "((())()(())())", "((()(())))()()", "(()()(())(()))", "()()((()()()))", "((())(()))(())", "()((())(()))()", "(()(())())()()", "()(()((()))())", "()(())((())())", "(()()()(())())", "(((()())()()))", "()()((())())()", "(()())()((()))", "(()())()(())()", "(()(((()()))))", "()((()()))()()", "()((())(())())", "((())(()))()()", "(()(()))((()))", "(()((()))(()))", "((()()))()()()", "()(((()()))())", "(()(()))()(())", "((()()(())))()", "(())(())(()())", "()(())(((())))", "()()()(())(())", "(()(())())(())", "((()))(())()()", "(()()(())())()", "(((())))(()())", "()(((())())())", "((())()((())))", "(((()())()))()", "()(()())()(())", "()()((())(()))", "()((())((())))", "((()))()()()()", "((((()())))())", "(())(()())(())", "((()((()()))))", "(()())(()(()))", "()(((())()))()", "()()()((()()))", "(((()))())(())", "((()()()())())", "(()(()))(())()", "(((()()())()))", "(((()(()()))))", "()(())((()()))", "((())(())())()", "()()(()((())))", "((()())())(())", "()((())()()())", "((()()))((()))", "()(()())((()))", "(((())))(())()", "(()())()()()()", "((())()(()()))", "(()(((())())))", "(())(())(())()", "(()(())()(()))", "()(((()())()))", "(()())(())(())", "((()())())()()", "(()(()))(()())", "((()()()(())))", "(()()()((())))", "(()())()()(())", "(()()(())()())", "()()()(())()()", "()(((())()()))", "()()()((()))()", "(()((())))()()", "(())(()()(()))", "()(())((()))()", "()()((())()())", "(()((())()()))", "(((()))()(()))", "((())(())(()))", "((((()()))))()", "(()(((())))())", "(())()()()()()", "(((())))((()))", "()(()())(())()", "()()(()(())())", "((())()(()))()", "(())(())((()))", "()((())()())()", "(((()((())))))", "(()(())()())()", "((()()(()())))", "((()()))()(())", "(())(()(())())", "((())()()(()))", "(())(())()(())", "(((()))(())())", "()()((()(())))", "((()()))(()())", "()((()((()))))", "()((()()()()))", "()()(())()()()", "()()(()(()))()", "((())(((()))))", "()(((()))())()", "()(())(()(()))", "()(()(())()())", "((())(()()()))", "()(())(()())()", "(()()())(()())", "()(()()()(()))", "(()())((()()))", "(()(()()()))()", "((()(()(()))))", "()(()())(()())", "(((()())))(())", "(())()(((())))", "(()((()))()())", "(((())))()(())", "()()()()()(())", "()(()(())())()", "((())()()())()", "(())()((())())", "()()(()()()())", "(()()((())()))", "(())()()()(())", "(((())()(())))", "(()())(()())()", "()()(()(()()))", "()((()()()))()", "()(()()())(())", "()()((()())())", "(((()))(()))()", "(())((()(())))", "()(((()))(()))", "(((()()())))()", "(()(())()()())", "(((())))()()()", "(())(()(()))()", "((())(()()))()", "(()(()((()))))", "(((()(())())))", "(())(())()()()", "(()(()()()()))", "((()()))(())()", "()()()()((()))", "(((()())))()()", "((()))()(()())", "()((((()()))))", "((()(())()()))", "()()()((())())", "(())()()((()))", "((())(())()())", "()(()(())(()))", "(((()()))(()))", "(((()))()()())", "(((()()()())))", "()(()((()())))", "(()(()))()()()", "(()()((())))()", "()(()()())()()", "((()))()(())()", "(((()))(()()))", "(()((()))())()", "(((())()())())", "(())(()(()()))", "()()()(((())))", "((()()(())()))", "()(()((())()))", "()()()()(())()", "((()()()))()()", "()(((()()())))", "(((((())()))))", "((((()))())())", "(()(()()(())))", "((()(())()))()", "(())()()(())()", "(())(()()()())", "(()(())(()))()", "(()()(()))()()", "(((()()))())()", "(()(()()())())", "()(((()))()())", "(())((()()()))", "((()))(((())))", "()(()(()))(())", "((()))()((()))", "((()(())())())", "(())()()(()())", "(()((()()())))", "(()()(()))(())", "((())()()()())", "((((()))(())))", "()(()((())))()", "()((()))()()()", "()((())(()()))", "()()((()()))()", "(()())(()()())", "()()((((()))))", "()((()()())())", "(((())((()))))", "(((()()()))())", "(()(())(()()))", "(((())()()))()", "()(())(()()())", "(())((((()))))", "()(((())))()()", "((((())))()())", "(())((()()))()", "(()())(((())))", "((()(())(())))", "(((()()(()))))", "(((()(()))()))", "(()((()()))())", "((()()()))(())", "((((()))()()))", "((())((()))())", "()(()()(()))()", "((()))((())())", "(((((())))()))", "()((()(()))())", "(()()((()))())", "(()()()())()()", "()()(())(())()", "(()(()())(()))", "()((()()(())))", "()(()(()))()()", "(()(())((())))", "((()())(())())", "(())()(()()())", "()((((())())))", "((()(()()))())", "((())())()()()", "(((())()()()))", "()(()()()()())", "(()()())((()))", "()()(())(()())", "()(()()(())())", "((())((())))()", "(()((())(())))", "()((()))()(())", "((((()))()))()", "()(())()()()()", "(()(())(())())", "(())((()())())", "((()())((())))", "(((((())))))()", "()(((())))(())", "(()(()())())()", "(()()())()(())", "(()()((()())))", "((()))((()))()", "(((())())())()", "(()()())(())()", "((((())())()))", "(()()()())(())", "()()(()())()()", "(())((())())()", "()((()))((()))", "((())())((()))", "((()())(()()))", "(((()(())))())", "()(()()((())))", "()()(()()())()", "(())()((()))()", "()((((()))))()", "()(())(())(())", "(()((()())))()", "((((()()()))))", "()(())()((()))", "((())()())(())", "(()(()())()())", "()()(())()(())", "()()(((()())))", "(()())((())())", "((()))((()()))", "(((((()))))())", "((())(()())())", "((()()())(()))", "()((((())))())", "()((()))(())()", "(((()(()))))()", "()(((()(()))))", "(())(()((())))", "()(())(())()()", "((()())(()))()", "(())((())()())", "(()()()()(()))", "(((()))((())))", "()()(()()(()))", "(((())())()())", "((())())()(())", "()()()()()()()", "((((()(())))))", "(())()((()()))", "((())((()())))", "()(()()()())()", "()()(()())(())", "(()((()(()))))", "(()())((()))()", "()()(())((()))", "((())()())()()", "((())(()(())))", "(()((()())()))", "()(())()()(())", "((()()())())()", "((()))(()())()", "((()(((())))))", "((()((()))()))", "(()()(()()))()", "(((((()))())))", "()(())()(()())", "((())())(()())", "(((())()))(())", "(())()(())()()", "(()()()()())()", "((()())()(()))", "(())((()))(())", "((((())()))())", "((()()())()())", "(()((())()))()", "()(((((())))))", "((()(()))()())", "()()(((())))()", "()((()))(()())", "((((()))))(())", "((()()((()))))", "((()()()()))()", "(()(((()))))()", "()(()(((()))))", "()((())()(()))", "(())(((()())))", "()((()())()())", "(((())(()())))", "(((())())(()))", "((((())())))()", "()((())())(())", "()()(((()))())", "(()()(()()()))", "()()((()))(())", "(())((())(()))", "(((()))())()()", "((()((()))))()", "((((()))))()()", "((())())(())()", "(()((((())))))", "(()(()(())()))", "(())(()())()()", "((()())()())()", "((()))(()()())", "()((()())())()", "()((((()))()))", "(())(((()))())", "(()()()()()())", "()(())()(())()", "(((())(()))())", "(()(((()))()))", "(())()(())(())", "((((()())())))", "()(()(()()()))", "((()(()))())()", "(()((())())())", "((((((()))))))", "((()())()()())", "()((()(())()))", "((()(()()())))", "((())((())()))", "((()))(())(())", "(()(()(())))()", "()((()(()())))", "(()(()()))()()", "(()()()(()))()", "((((())))(()))", "(()())()(()())", "()((()())(()))", "((()(()())()))", "(()()(()(())))", "(((()())())())", "()((())())()()", "(())()(()(()))", "((()((())))())", "(((())(())))()", "(()()())()()()", "(())(((())))()", "()(()(()()))()", "()()()(()()())", "((()(()))(()))", "(()()(((()))))", "((()))(()(()))", "()((()(())))()", "((()(())))(())", "(()(()(()))())", "()(()()(()()))", "(()()(()())())", "()()()(()())()", "()(()(()())())", "((((())))())()", "(()()()(()()))", "((()(()())))()", "()()(((())()))", "(())()(()())()", "()((()()))(())", "((((())()())))", "(((())(())()))", "()()((()))()()", "((()()()()()))", "(())(((())()))", "(((())()))()()", "(((()())(())))", "(()(()()))(())", "(())((()))()()");
        }else{
            return Arrays.asList("(())()((()()))()", "(()()((()))(()))", "()()((())()()())", "()(()((())))()()", "((()(()()))()())", "((((()()))()))()", "(((())())((())))", "((()()()))()(())", "((()(()())()()))", "(()()())()(())()", "(()()(((()()))))", "()()()(()((())))", "()(((()))())(())", "(()()(())())(())", "()()((())(()()))", "()(((())))(())()", "()(((((())()))))", "((()(()((())))))", "((()()()(()))())", "((((()(())))()))", "(((())()())())()", "(())((())(())())", "((())()()(())())", "(()(()))()(())()", "(()(()((()()))))", "(()())(()()()())", "((()))(())(()())", "()(((()()))(()))", "()()(())(()()())", "()(())((((()))))", "(())((()())(()))", "((((()))()()))()", "(((())))(((())))", "((()()))()()(())", "()((())()()()())", "(()()())(())(())", "(())(((())(())))", "((()((()()))()))", "((()()(())))()()", "((()))(()()(()))", "()(()())()()(())", "()()((()()))()()", "(((()())))()()()", "(((()))())()(())", "()()(((())()))()", "((((())(()))()))", "()(()()()()()())", "(()())((()))()()", "(((()((())))()))", "((())(()(()))())", "(()(()()))()(())", "()()(()())()()()", "(((()))()())(())", "()((()()(())()))", "(((()())(())))()", "((())())(())(())", "()(()()()(()()))", "((())())()(())()", "((())(((()()))))", "()(())(()()(()))", "(()((()())())())", "()(()(()))()(())", "(((())(()()))())", "(()(()()(()))())", "(())(((()()())))", "()()()()()((()))", "((())(((())())))", "(())()()()(()())", "(()(()))(())(())", "(())()()((()()))", "()(()(()(()))())", "(((((())))(())))", "((()())(()))()()", "()(((()())()()))", "((())()(())(()))", "(()()(()))(())()", "(()((()((())))))", "()()(())((())())", "(()(()((())())))", "((()())()(())())", "(((()()(())))())", "(((((()))()())))", "()()(((()())))()", "()((()((()))))()", "((()(((()())))))", "((()(()))()())()", "(()(())(())(()))", "()(()(((())())))", "((()))(()(()()))", "()()(()(()(())))", "((())(()))()(())", "(())(()((())))()", "()((())(()))()()", "(((()(()))()))()", "(()()()(())()())", "()()()((()))(())", "(()()())(()())()", "()(())(()())()()", "((()(((())()))))", "((()()()))(())()", "(()())(()()(()))", "((()())()()()())", "(((()(()))(())))", "((()))((()))()()", "()(((((()())))))", "((()()(()))(()))", "((()(()()))(()))", "()()((()))(()())", "((())()(()))()()", "(()())(())(()())", "(()())()()()(())", "(()()()(()()()))", "(()()())()()(())", "(())((()()))()()", "()((()()))()(())", "((()))(()()()())", "(((()())()()))()", "()(())(())((()))", "((((())(())))())", "()(((((()))())))", "(()()(((())())))", "(()()((())))()()", "(((()(())())))()", "(())()()(()(()))", "()(()(((()()))))", "((()()))()(())()", "()(((()()))()())", "()()()()(())()()", "(()(()))()()(())", "(())()(()((())))", "(((()))())(())()", "()(((()((())))))", "(()(()(())))()()", "(()(()())())(())", "((()()()(())()))", "((((()())())))()", "(((())(())())())", "()(((())(()))())", "((())()()(()()))", "()()((())(())())", "((())((()))(()))", "(((()(())))())()", "(()((())))(())()", "()(()(())())(())", "()((()()()())())", "()()(())((()()))", "()()()()((()()))", "()(()(()))(())()", "()(((()(()()))))", "()()()(()(()))()", "((())())(()())()", "(()((()()())()))", "(()(()(())()()))", "(())()()((())())", "(((())(()())()))", "(()((()())()()))", "(((((()))(()))))", "(())(())((())())", "(((()()())))(())", "()(()()()(())())", "(()((()))()())()", "(())(((()())))()", "()((((()()))()))", "()((())(())(()))", "(()(()(((())))))", "(()(())()(())())", "(())((())()()())", "((()))((((()))))", "(()(((()())))())", "((())(()()())())", "(((()))()()())()", "()(()(((()))))()", "((((())))((())))", "(())((()()()()))", "()()((())()(()))", "(()()()()()()())", "()((())()(()()))", "()(()()()()(()))", "((()()))(())(())", "(((()(((()))))))", "()(((())))()(())", "(()(())(())()())", "()()()((())())()", "((()(()())())())", "((()()((())())))", "()(())(((()())))", "()((()()(()))())", "(()(()()))(())()", "(())()()()((()))", "((()((())()))())", "()(()(()())()())", "(((((()))())))()", "((((())))())()()", "(()()()(()())())", "()(((()())())())", "(()())()(())(())", "(()()()()(()()))", "(())(()(()()))()", "((()(())))()(())", "(((()())))((()))", "((()))(()(())())", "()((()())())(())", "(())()((()))(())", "((()()(((())))))", "(()())((())(()))", "()()(()())((()))", "(()()((()())()))", "()((()()()()()))", "((())((()))()())", "(())(()())(()())", "(()()(()(())()))", "()((()(()()())))", "(()())(()())()()", "(()())(((()())))", "(()(()()()())())", "(()(()())()())()", "((())(()(())()))", "()(())((()))()()", "((()()())()())()", "(((()()))((())))", "((())((()(()))))", "(())((((()))))()", "()(()()(()()()))", "((()())(()()()))", "(()(((()))))(())", "((()((()))))(())", "(((())())()())()", "((((((()))))))()", "(()((()))())(())", "(())(()(((()))))", "(()()(((()))))()", "(())()(((()())))", "()()((()(()())))", "(())((())()(()))", "(((())()(())))()", "()(()((()(()))))", "(()(((())()))())", "(())((()())()())", "()()((()())(()))", "()((()()())()())", "((()))()(())(())", "()()((())())()()", "()(((((())))))()", "(()(()(()))()())", "(()((())())())()", "(()(((((()))))))", "()()()(((())))()", "(((()()()))())()", "((()()((()))))()", "()()(())()((()))", "((())()(()()()))", "((())()()()()())", "()(())(((())))()", "(()(()())(()))()", "(())(())()(()())", "((((()()))))(())", "(((((())()))))()", "(((())(((())))))", "()()()()(()()())", "(()()(())()())()", "()((()(()))(()))", "((()())(((()))))", "()((()))(()())()", "()((()(((())))))", "()((((())())()))", "()((((()())))())", "((((()))(()())))", "((()()()())()())", "((()))(())()()()", "()(())()(()()())", "(()((((()))())))", "((((()))())())()", "((((()((()))))))", "((((()(()))))())", "()((())())((()))", "()(((())()))(())", "(()(())())(()())", "(()()((((())))))", "()(()(()(())()))", "()((())()(())())", "((()(())))(())()", "()((()())()())()", "(()()(()()))(())", "(())()((())())()", "(()(()()()()()))", "((()())()(()()))", "()()(((())(())))", "()((((())()))())", "((((())())())())", "((()())(()())())", "((((()())))())()", "()((((()))))(())", "((()((())())()))", "()(()(()())(()))", "((()((()())))())", "(((()))()(()))()", "()((())())(()())", "()(((()()(()))))", "(()()(()())()())", "()(())()(())(())", "((())())()()(())", "(())(()()(()()))", "(()()()()(())())", "()(()())()(())()", "(()(((())))())()", "(())(()())()()()", "(((())((()))()))", "((()(()))(()))()", "((()))((()(())))", "(((()())()(())))", "(((())()()))(())", "(())()(((())))()", "(()()(()(()))())", "(((()()))(()))()", "(())(()())((()))", "((()()())())(())", "((()(()))((())))", "()()(())()(()())", "(()())(((())))()", "()(())(())(()())", "()((()((())())))", "((((()))()))(())", "(()(()(()))(()))", "(())()()(()()())", "((((()())()())))", "()()()()(()(()))", "(((()(()()))))()", "((()))(())((()))", "((()()()())(()))", "(()((((()())))))", "(()(()))(()())()", "()((()(()())))()", "()((()(())))()()", "(())()(()())()()", "()(((())(())()))", "(()(())((())()))", "(())(()(()(())))", "(()(())(()))()()", "()()(()(((()))))", "(((()))(()())())", "(()((())()))(())", "((((()))(())))()", "()(()((())(())))", "(()((())(()))())", "(()()()())()(())", "(())((()(()())))", "((()(()(()()))))", "((())(()))(())()", "()()(()(()()))()", "(((())())())()()", "()((((((()))))))", "()(()()(((()))))", "((())((())()()))", "(()((((())))))()", "()()((()(())))()", "(()(()(()()())))", "((())()(())()())", "((())())((()))()", "()((()))(())(())", "((())()()()(()))", "((()())((()))())", "()()(()()(()()))", "()(())()()(()())", "(((()))(())(()))", "((()(()()(()))))", "()(()()(()(())))", "()((((())))())()", "((()()())(())())", "(((())()))((()))", "(()()((()()())))", "(((()))()((())))", "()()()(())((()))", "()()(()()()()())", "((((()(()())))))", "((((())))()())()", "()(())()(()(()))", "(())()(())(()())", "()(()()())()()()", "(())(())(())()()", "(((()()())()))()", "((()()(())(())))", "((())()((()())))", "(((()()))()()())", "((()))((()()))()", "()()((()()())())", "(())(()(()))(())", "()(()(()()))(())", "(()())()(()()())", "(((((())))))(())", "((((())()))()())", "((()()()()))(())", "()(()()((())))()", "(((((())()()))))", "((()((()))()()))", "()(()((())())())", "((()())())()(())", "((((())())()))()", "(()()()())((()))", "(())((()(()))())", "()()((()(())()))", "()()((((())))())", "((()(((())))()))", "(())(()()(())())", "(()()(()())(()))", "((((())((())))))", "(((((()(()))))))", "(()(())((()))())", "((()))((())()())", "((())(()())())()", "(())()((((()))))", "((((((()))()))))", "(()(((()))())())", "()((((()))()()))", "((((()))))(()())", "(((())())())(())", "(()(()()())())()", "(())(())()()(())", "(()())((()()))()", "()(((()()()())))", "()(((()))((())))", "((()()(()()))())", "()(())((())()())", "((((()()()))()))", "(()()(())((())))", "(()((()(()))()))", "((())())((())())", "(((())(()))(()))", "()((()())(())())", "((())((()())))()", "()(()(())()()())", "()(()(())(()))()", "(((()(()())))())", "(()(()))((())())", "()((()))((()()))", "(())()()()()()()", "((())()()())()()", "((()(())()())())", "(()())()((()()))", "((())()(()(())))", "(()(((()(())))))", "(()(()(()())))()", "(())()(()())(())", "()((()(())(())))", "()((())((())()))", "(()((())(())()))", "()()(()())(()())", "()(()((()())))()", "(()(())(()(())))", "()(()(())((())))", "()()((()))()(())", "((())()())()()()", "(()())((())()())", "((()(())(())))()", "((()(()(())))())", "()(()()((()())))", "()(()()()())()()", "((()((()))())())", "()((()(()))()())", "(((()())))(()())", "()()(()()()(()))", "((())()((())))()", "(((()()())(())))", "(((())(())))()()", "()((())(()()))()", "(()((())()()()))", "()()((((()))()))", "(()()()())(()())", "(()())()((())())", "(((())()((()))))", "()(())()((()()))", "(((()))(())()())", "((())(())(()))()", "(())((((())))())", "(((((((())))))))", "()((())((()))())", "((()((((()))))))", "((((())()())()))", "(()(())()())(())", "((((())))())(())", "((()())())(())()", "(()(((()))()()))", "()()(())()()(())", "()(())(()(())())", "((()(()()()())))", "()()()(((()))())", "()()()((()(())))", "(((()()()())))()", "((()))()()(()())", "((()((())))())()", "()(())((())(()))", "(()())()(()(()))", "((()()(()())()))", "()((()()()))(())", "(()((()(())))())", "(())(())()(())()", "((()))()(()())()", "(()(()())(())())", "((((()())(()))))", "(((((())())))())", "()((()())(()()))", "((())((()()())))", "(())(()(()()()))", "((())((())(())))", "((()))(((())()))", "((())(()()))(())", "()(()((())()()))", "(((()(()))))(())", "((()()(())()))()", "()((((()(())))))", "(()(((())())()))", "()(()())((()))()", "()()()(()())(())", "((()(())()()()))", "(())((()(())()))", "((())()(((()))))", "()((())(()(())))", "(()()((()())))()", "(()(())())((()))", "()()(()()(())())", "()((((()()()))))", "()((())())()()()", "(())()(()()())()", "()(()()())((()))", "(()()((())())())", "(((())()))(()())", "(())(())(()(()))", "(())(()()()()())", "((()()))((())())", "()(((())())())()", "()(()(())()(()))", "(()()())(((())))", "(((())))(())(())", "(((())))()((()))", "(()()(()()()()))", "()()(())(())()()", "(())(((())))(())", "()(((()(()))()))", "((((()()())))())", "(((())((())())))", "((((())()()))())", "()()()()()()()()", "(())()(()(())())", "()()(((()()())))", "()(((()))(()))()", "(()((()))((())))", "((()()(()(()))))", "()(())((()(())))", "(()(()(())()))()", "(((()(())()())))", "(()())(())((()))", "((()()()()()))()", "()(())(())()()()", "((()))()()((()))", "(()()(()()())())", "()(()(()()()()))", "()(()((()))())()", "((()())(())()())", "(((()(()()()))))", "((()()))(()())()", "(((())(())()))()", "()(((()(())))())", "()(()())(()(()))", "(((())))((()()))", "(())()()(())()()", "(()((()())))(())", "((()(()))())()()", "(((((()())))()))", "((()(()())(())))", "()((()))()(()())", "((()))((())(()))", "()()((((()()))))", "((((()))))((()))", "((()))(((()))())", "()()(()((()())))", "((((())))(())())", "(((()()))())()()", "(()(())()()())()", "()()(()(())())()", "()(())()((())())", "(((())())(()()))", "(()((()()()())))", "((()(()()())))()", "()(()()(())())()", "(()(()(()(()))))", "()()((()()()()))", "((())(())()()())", "()()()(())()()()", "((()()()((()))))", "()()()(()()())()", "(())((()()())())", "()((())(((()))))", "(()(())()(()()))", "()(((())()())())", "((())(((()))()))", "()()(())(()(()))", "()(())(()(()()))", "((())()())(()())", "(()((())))()(())", "(((((())))()()))", "(())(()()()(()))", "((()()))((()()))", "((((())(())())))", "()()(((())))(())", "(((())()()()))()", "(()(()((()))()))", "(()(()()))(()())", "((()))()((())())", "((((()()))(())))", "()((()()))((()))", "(((())))()()()()", "(())(((())()()))", "((()())()())(())", "(()()())(()()())", "((()())((())()))", "((()(())()))(())", "(((())))(()())()", "(())(())((()))()", "(()((()(()()))))", "(())(((()))())()", "(()())(()(())())", "(())(())(()()())", "(((()))((())()))", "(()()((())()()))", "(((()))(()))()()", "()(()()())(()())", "(((()())()))(())", "(()()()((())))()", "(())()(())((()))", "(()()())((()))()", "()((())()())(())", "()()()(()(()()))", "()()(()()())()()", "((())(()()()()))", "(())((())(()))()", "(()()()()()(()))", "()(()())(()()())", "((((()))()(())))", "(()(()))()(()())", "()((()))()((()))", "((()))(()())(())", "(()(())())()()()", "(()())((((()))))", "((()()))()()()()", "((((()))))()()()", "(()()()(()))(())", "(())(()(())())()", "()(())(()()())()", "(((((()))))())()", "(())((()))(())()", "()()()((((()))))", "((()(())())())()", "()((()(()(()))))", "()()()((()()))()", "()(()((())))(())", "(()())((()(())))", "()()()()((())())", "((()()()))()()()", "(()((()))(()))()", "((())(((())))())", "(()())()()(()())", "((((()))((()))))", "((()()())(()()))", "()(())()()((()))", "(()((()()))())()", "()(()(()()())())", "()((())(())()())", "((((())()))(()))", "()(())((()()))()", "(((())()))()()()", "(((()(()))()()))", "(((()()))()(()))", "()()(()(()))(())", "()()()()()(()())", "(((((()()))))())", "(()((((())()))))", "(())((((()()))))", "()()(((()))())()", "()((()))((())())", "((()((()()()))))", "((((())))(()()))", "(()()(())(()))()", "()(((()))()()())", "((())()())((()))", "((()(())(()())))", "(()()()()())()()", "()(((()()())))()", "(()(()(())(())))", "(((()((()))))())", "()()(()((())))()", "((()(((()))))())", "(())()((()(())))", "(())(()()())()()", "((())(())()(()))", "(()(()()()))(())", "(((()())(()())))", "()((((()))())())", "((()(()(()))()))", "(())()(()(()()))", "((()()()()(())))", "(())((()))()(())", "()((()(())()))()", "(()(())(((()))))", "(()()()((()())))", "(((()())())())()", "(((())()()(())))", "(())()(())()()()", "()((())()()())()", "(()((())()())())", "()(((())()()()))", "()(()((()()())))", "(((()))((()))())", "(()(())(()()))()", "((())())(())()()", "(()())(()(()()))", "(((()()(()))()))", "((()()(()))()())", "(())(()((()())))", "(()())(())()()()", "(()(()()(())))()", "(()()(()))()(())", "((()))()()()()()", "((()())(())(()))", "()((()()))(()())", "()(((()())))(())", "((()))()((()()))", "(((())(()))()())", "()((()()))()()()", "((()()))(())()()", "(((()())()())())", "((()())(()))(())", "((((())(()))))()", "((())(())())()()", "(()(()()(()())))", "(((()((())))))()", "(()((()())()))()", "()()(()(()())())", "((())((())))(())", "(())(((()()))())", "(())(()())()(())", "()()(())((()))()", "(((()())(())()))", "()((()()(())))()", "(((()))()())()()", "()()()()(())(())", "()(()()()(()))()", "()((()((())))())", "()()(()((())()))", "((())())()((()))", "(()(()(())))(())", "(()(()())())()()", "()()()()()(())()", "(()()()(())())()", "((((()))(())()))", "(((((()))()))())", "()()(((())())())", "()(())(()())(())", "()((())()(()))()", "(())(()((()))())", "((()(())))(()())", "()(((())((()))))", "(()()(()))((()))", "((((())()(()))))", "()()(((()())()))", "(())()((())()())", "((())(()))((()))", "()()()((())(()))", "()(()(()))()()()", "(((()()(()))))()", "((((()())))()())", "(()((()))()()())", "((())()(()))(())", "((()(()))()(()))", "(()(()()))((()))", "(((()))((()())))", "(()((())()))()()", "(()(())(()))(())", "(())()((()()()))", "()(()(((())))())", "()((((())()())))", "((()()()))((()))", "(()()((()))())()", "()(((()))()(()))", "()(()()(()))(())", "((()(()())()))()", "(((((()()))())))", "(()()())()(()())", "(())((())((())))", "((()(()()))())()", "(((())())(())())", "()()((())(()))()", "((((()()(())))))", "()(()(())())()()", "(((()(())))()())", "(()(()))()((()))", "()(())(())(())()", "((()((())(()))))", "()(()(()()(())))", "(((()(())())()))", "(((())(()()())))", "()()(((()))()())", "()((()))()()()()", "(((()()()(()))))", "(((())(())(())))", "()(()())()((()))", "(()()())(())()()", "()(((()()))())()", "((((()()))())())", "(())()()(()())()", "((()(()))(()()))", "((((()))()()()))", "(((()))())((()))", "(())()(((())()))", "((()()()(())))()", "(())((()()))(())", "((())(()(()())))", "(()()()()((())))", "(()(((()()))))()", "((())()()(()))()", "((()))(()()())()", "()((((())(()))))", "(()())()()()()()", "(())(((())())())", "((()(())()))()()", "(((())()())()())", "()(()(()))((()))", "((())())(()(()))", "()()(((())()()))", "(()((()()())))()", "(()(())()(()))()", "(((())(()())))()", "()()()((())()())", "(()(((()())())))", "()()(((((())))))", "((())(()()(())))", "(()((()))()(()))", "()()(()(())()())", "(())(((()())()))", "()((((()()))))()", "(((()()())))()()", "()(()(()(()())))", "(((())()()()()))", "()(()()()((())))", "(()(((()))))()()", "(((()))()()(()))", "()((())(()))(())", "(()((())))(()())", "((()())()((())))", "((())(()))()()()", "(())()()((()))()", "()()()(()(())())", "()()((())()())()", "()(()()()()())()", "()((()()(()())))", "((((())())))()()", "()()(()())()(())", "(()())()(())()()", "((()(()))()()())", "((()((())()())))", "(()()(()((()))))", "(((((())))())())", "()((()((()))()))", "(()(())(())())()", "(()()(()))(()())", "((())(()((()))))", "()(((()))())()()", "(()(()((())))())", "(())()()()(())()", "(())(()((())()))", "((()()((())))())", "(((()()(())())))", "(((((()))())()))", "(()()())(()(()))", "(()(()))(())()()", "()(())(((()))())", "(()())(()()())()", "()(()())(())()()", "(()())()()((()))", "(()())(())(())()", "((()(())((()))))", "((((()()))()()))", "(()()())()((()))", "()(())()()()()()", "(((())(()(()))))", "((()())()()())()", "(()(()))()()()()", "((()()))(()(()))", "()(()())()()()()", "(((()(()))())())", "((((((()()))))))", "((((()))())()())", "((()()(())))(())", "(()(((())(()))))", "()(((())))((()))", "(((())())()()())", "((())()(()()))()", "((()()()))(()())", "((()(()())))(())", "(((()())()()()))", "(()(())()((())))", "(((()))())(()())", "(()(()())()(()))", "((())(()(())))()", "()(((())(()())))", "((()()))()((()))", "()((()())())()()", "()()((())((())))", "()()((()))(())()", "()(((((()))))())", "()(())(())()(())", "((())())()(()())", "(()()((())))(())", "(())()()(())(())", "((((()())())()))", "(((()(())()))())", "(())(())(((())))", "()((()()()(())))", "((())((()))())()", "(((()(())))(()))", "(((())))((())())", "(()(((()()()))))", "(())((())()())()", "(((())()(())()))", "(()(()))((()()))", "(()()(())()()())", "(()(()))(()()())", "((()(()))(())())", "()(()())()(()())", "()()((()())())()", "(()((())())(()))", "(())()(((()))())", "()()()(((())()))", "(()()(((())))())", "(((()()()))(()))", "((()()((()))()))", "((((()())()))())", "()(((())()))()()", "(()(((())()())))", "((())())(()()())", "()(((())(())))()", "(()((()))())()()", "((()))(())()(())", "(()(()())(()()))", "()(()(((()))()))", "(((()()()()())))", "()()(())()(())()", "(()()(()()))()()", "((()))()(())()()", "()((()()())())()", "()((((()())())))", "()((()(()))())()", "((((()(()))())))", "(()((())(()())))", "(())(((((())))))", "()((()))(()(()))", "()((((())())))()", "((())((())()))()", "((((((())())))))", "()()((())())(())", "()((())()((())))", "((((()))())(()))", "()((())())(())()", "((())())((()()))", "((())()()()())()", "(((()))()()()())", "()(())()(())()()", "(((()))(()()))()", "((((()))(()))())", "()((()())()(()))", "((()))(()((())))", "()(())((()))(())", "((()()))()(()())", "((())(()))(()())", "((((()())))(()))", "((()((()())())))", "(((()((())()))))", "(((()())))(())()", "(((())()()))()()", "()(()(()())())()", "((()((()))))()()", "(()()()(()()))()", "()()(())(((())))", "((()((())())))()", "(()())((())())()", "(((((())(())))))", "()((()()()()))()", "(()((()())(())))", "()((()()((()))))", "(()()(()(())))()", "()(()(()))(()())", "(()(((())))(()))", "((()()())()(()))", "((((()()()()))))", "(((())((()))))()", "()((()(()()))())", "()((((()))))()()", "(()(()())()()())", "((()(())))()()()", "((()())(()()))()", "((((((()))))()))", "(()())(()())(())", "(((()))(((()))))", "(((())())()(()))", "(())(()())(())()", "(())()((()))()()", "(()(()()((()))))", "(()()(((()))()))", "(((()(()(())))))", "((()))(())(())()", "(()(()(()))())()", "(((()(()()))()))", "()()()()(()())()", "()(((((())))()))", "((()()()())())()", "()()((()(()))())", "(()(()))(()(()))", "(((()))(()(())))", "(())((())())(())", "(()(()()()(())))", "(((())))()(()())", "()((()))(())()()", "(()())(((()))())", "(()(())((())))()", "((((((())))))())", "()()((()()))(())", "()(())(((())()))", "()(((()())()))()", "(((((())()))()))", "((())()(())())()", "((()(())()(())))", "()(()())(((())))", "(()()(())()(()))", "(()((((()))))())", "(((((()())()))))", "(())(()(()())())", "((((()))()))()()", "()()(()(()()()))", "(()(()()))()()()", "((())()()())(())", "((()))(()(()))()", "()((()(())))(())", "(((()()()))()())", "()(((()())(())))", "()()()(())(()())", "(()()()())()()()", "(()((())(())))()", "()(((())))(()())", "((())())()()()()", "()(()(()(())))()", "()(()(()()))()()", "((((())())(())))", "(()()(())())()()", "((()(())))((()))", "((()())(()(())))", "(()()(()(()())))", "()((((())))(()))", "(()()()()(()))()", "((()())()(()))()", "((()()()(()())))", "(()(()()()()))()", "(())()((())(()))", "(()()()(()(())))", "((()())())()()()", "((()()())())()()", "()(())()(()())()", "(((()))()(()()))", "((((()(())))))()", "()()()((()))()()", "(((()))())()()()", "(((())()())(()))", "(((()()))(())())", "(((()())))()(())", "((())(())((())))", "(())(()()(()))()", "(()())((()))(())", "(((())()(()))())", "(())((()())())()", "(()(((())))()())", "(())((((()))()))", "((()((()()))))()", "((()((()(())))))", "()(()()(()()))()", "(()()(()())())()", "(((()()(()()))))", "(())(())()((()))", "()((()(())())())", "((())(()())(()))", "(()())(((())()))", "()((()())(()))()", "()()(())()()()()", "(()(()()())(()))", "((())())(((())))", "(()(())((()())))", "((()((())))()())", "()((()(()())()))", "((()(())()()))()", "((((()()()))))()", "()((()()()))()()", "(((())()(()())))", "(()(()))(((())))", "(()((()(()))))()", "((())()())()(())", "((()()))(((())))", "((()(()(()))))()", "()()((()))()()()", "()((()())()()())", "(())()(()()(()))", "(()(()(()()))())", "()((()))((()))()", "(((())(())))(())", "(()(())())()(())", "()()()(()())()()", "(())((())())()()", "((())(())(())())", "(()((((())))()))", "(()()()()())(())", "(()())()((()))()", "()((())((())))()", "((())((()()))())", "((()(())())()())", "(((())((()()))))", "(((())))()(())()", "()(()((()())()))", "(((()))()(())())", "()()(()()(()))()", "(())(()()((())))", "(((()))(())())()", "((((())))()()())", "()()(()()()())()", "(((())()))(())()", "((((((())))())))", "(()((())()()))()", "((())()((()))())", "()(((())())()())", "()()((()()(())))", "(((())))(())()()", "(((((()))))(()))", "()(()()(()())())", "(())(((())))()()", "()()()(())(())()", "(((()()())()()))", "()(())(()((())))", "((()))()(()()())", "()()((((())())))", "((()())())((()))", "((()((()))()))()", "(((()(()))))()()", "(((()(())(()))))", "(((()()()())()))", "(()()()())(())()", "()(()())((())())", "((()()())((())))", "((()(((())))))()", "()(()()((()))())", "((()))((()())())", "(()())()(()())()", "(((()()))(()()))", "(((()((()())))))", "(((()()))()())()", "(()(())()())()()", "(())(()(()))()()", "(((()))(()()()))", "()()()(()()(()))", "((()()()()))()()", "((((()()))))()()", "(((())))()()(())", "(((((())))))()()", "(()((())())()())", "((()))(((())))()", "()((())())()(())", "((()()())()()())", "(()((()(())())))", "()(()((())()))()", "(()()((()(()))))", "(()(((())())))()", "()(()())((()()))", "((()()))((()))()", "(()())((()()()))", "((())((())())())", "(())((()(())))()", "(((()())((()))))", "(((()(()())())))", "(()(())())(())()", "(())((()((()))))", "()(((()))(())())", "(((())))(()(()))", "(()()())((())())", "((()()(())())())", "()((((())))()())", "(())(((()))(()))", "(()()()(((()))))", "((())(()()))()()", "()()(((())))()()", "(()(()(()())()))", "()(((())())(()))", "((((()()())())))", "()(()(())()())()", "(()()(()()()))()", "(())()(()()()())", "(())()(())(())()", "()(()()())()(())", "()()(((()(()))))", "()(((()(()))))()", "(()()((())(())))", "(()()((()()))())", "((()))()(()(()))", "(())(())(())(())", "(((()()())())())", "((()(())(())()))", "(())((((())())))", "((()()()()()()))", "(((())((())))())", "()(()(())(())())", "((())()((())()))", "(()(()))((()))()", "(())()()()()(())", "(((()()()()))())", "()((()))(()()())", "()()((((()))))()", "((((())))()(()))", "((()))()()(())()", "((())(())(()()))", "(((()())()))()()", "()((())()())()()", "()()(()()())(())", "()(()()()())(())", "()(()((((())))))", "()()(()())(())()", "((()))((()()()))", "((()(()()()))())", "()(()()(())()())", "()()()(())()(())", "((((()))))(())()", "(()(((()))()))()", "()()()(((()())))", "()((()()())(()))", "()()((()())()())", "()((())(()())())", "(()(()()())()())", "(()(())()()(()))", "((((())())()()))", "((()((())))(()))", "(()(()())((())))", "(((((())())())))", "()(())((())())()", "(()((()()(()))))", "((()()(()())))()", "(()((()())))()()", "((()((()))(())))", "(()((())))((()))", "()()()((()())())", "()()(((()))(()))", "()()()()((()))()", "((((())())))(())", "((()())())(()())", "((()))()(((())))", "((())(((()))))()", "(())()(())()(())", "((()(((()))())))", "()(())(()(()))()", "(()())()()(())()", "((()()(())()()))", "()(()(()((()))))", "()(((())))()()()", "()((())(())())()", "(()()(())(()()))", "(((((())))()))()", "(())(()()()())()", "((()())()()(()))", "()(((()()())()))", "()()(()()((())))", "(()(()((()))))()", "((())(())()())()", "()((()()))(())()", "(())(((()(()))))", "()()(())(())(())", "((()(())(()))())", "(())(((())()))()", "(())((()()()))()", "(((((()()())))))", "(((()())())(()))", "((()))(()())()()", "(())(())((()()))", "()(()()())(())()", "(())(())(()())()", "(()()((())()))()", "()()((()))((()))", "(())(((()))()())", "((()(()(())())))", "(())()()(((())))", "(()(()()(())()))", "(()()()((())()))", "(()()())((()()))", "(((())))(()()())", "(())((()))(()())", "(()()())()()()()", "(()())(()((())))", "(((())()()())())", "((())(()()()))()", "()(((())()(())))", "((())()(()())())", "(()()()()()())()", "((()(()())))()()", "(())((())(()()))", "()((()))()(())()", "()((()((()()))))", "(()())()(((())))", "()(((()))(()()))", "()(()((()))()())", "(())(()(())()())", "()((())((()())))", "(()(())(()())())", "()((())(()()()))", "(()()()(()))()()", "()((()())((())))", "()(())((()())())", "((((())(()()))))", "(()(())()()()())", "((()()(()))())()", "(()()(()))()()()", "()(())()((()))()", "(()())(())()(())", "((()))()()()(())", "(((())(())()()))", "((()(())())(()))", "(((())))((()))()", "()(((()())))()()", "((((())()())))()", "(()((()()()))())", "()(()())(())(())", "((()))((()))(())", "(()((()()))(()))", "()()()()()()(())", "()()(()(())(()))", "()(())()()()(())", "(()((()))(())())", "((((()))))()(())", "(()(((()))(())))", "()()(()((()))())", "((()(()()())()))", "()(()()(())(()))", "((()(()))())(())", "()()((()()()))()", "(())((()))()()()", "(())(()()())(())", "()((((()))()))()", "(()((())((()))))", "()(((()()()))())", "((()()(()()())))", "()(((()))()())()", "()()(())(()())()", "((((())))(()))()", "(()()(())(())())", "(((()())(()))())", "((())()())(())()", "(((()()((())))))", "(()()()((()))())", "(()((())()(())))", "()(()((()()))())", "(())()(()(()))()", "(((())(()))())()", "((()())((())))()", "(()()((()))()())", "(()(()(())())())", "((())((()())()))", "()((()(())()()))", "((())(())())(())", "((()()()()())())", "()((())()()(()))", "((()()((()()))))", "((())((())))()()", "(()(())(()()()))", "()(((())()()))()", "()(()(())(()()))", "(((()))((())))()", "(()())(()(()))()", "((()())((()())))", "(())(())()()()()", "(((()())())()())", "((()()))(()()())", "()((()))(((())))", "(()(()()()))()()", "(()(((()()))()))", "()()((()((()))))", "((()())(())())()", "(())((()()(())))", "((()))()((()))()", "((()())()())()()", "((())((((())))))", "(()()(()()(())))", "(((((()))))()())", "()((()))()()(())", "()(())(()()()())", "(()((()()))()())", "()(((()(())())))", "((((())()()())))", "()()(((()()))())", "()()()()(((())))", "(())(()(())(()))", "()((((()))(())))", "(((()))(()))(())", "()(()((()))(()))", "((((()))()())())", "()(()(()()()))()", "()()(()(()))()()", "(())((()))((()))", "((()))(((()())))", "()(()())(()())()", "(()()()(())(()))", "(((())()))()(())", "((()))((())())()", "()(())()(((())))", "((())(()())()())", "(((((()())))))()", "()()()((()()()))", "(())()((()())())", "(((()((()))())))", "((((()(())()))))", "()()()(()()()())", "()(()()((())()))", "(()((()))(()()))", "(()((())))()()()", "((()()())(()))()", "(((()()))())(())", "()(())()()(())()", "()(()()(()))()()", "((())()()((())))", "(((())())(()))()", "(()())((()())())", "()(())((()()()))", "((((())()))())()");
        }
    }
}

